#include "KamaCoder.h"
using namespace std;

void KamaCoder53::init() {
  // 初始化并查集
  for (int i = 0; i < m_n; i++) {
    father[i] = i;
  }
}

int KamaCoder53::find(int x) {
  // 路径压缩
  if (father[x] != x) {
    father[x] = find(father[x]);
  }
  return father[x];
}

void KamaCoder53::join(int x, int y) {
  // 合并并查集
  x = find(x);
  y = find(y);
  if (x != y) {
    father[x] = y;
  }
}

int KamaCoder53::krushkalrun() {
  // 输入数据
  int v, e;  // 顶点数和边数
  cin >> v >> e;
  int x, y, k;         // 边的起点、终点、权值
  vector<Edge> edges;  // 边的集合
  while (e--) {
    cin >> x >> y >> k;
    edges.push_back(Edge(x, y, k));
  }

  // 执行krushkal算法
  // 按边的权值从小到大排序
  // Lambda表达式的基本语法如下：
  // [捕获列表](参数列表) -> 返回类型 { 函数体 }
  /*
  捕获列表 是空的，表示Lambda表达式不捕获任何外部变量。
  参数列表 是 (Edge a, Edge b)，表示Lambda表达式接受两个Edge类型的参数。
  返回类型 是隐式的，编译器可以根据返回语句自动推断。
  函数体 是 return a.val < b.val;，表示返回两个Edge对象的val属性比较结果。
  因此，[](Edge a, Edge b)
  这部分代码定义了一个匿名函数，用于比较两个Edge对象的val属性。
  */
  sort(edges.begin(), edges.end(),
       [](Edge a, Edge b) { return a.val < b.val; });

  // 初始化并查集
  init();

  int result = 0;
  // 从头开始遍历边
  for (Edge edge : edges) {
    // 查询当前节点是否在同一个并查集内
    int fx = find(edge.left);
    int fy = find(edge.right);

    // 如果不在同一个并查集内，则合并并查集
    if (fx != fy) {
      result += edge.val;
      join(fx, fy);
    }
  }
  cout << result << endl;
  return 0;
}

// 主函数，用于处理输入和输出结果
int KamaCoder53::run() {
  // 输入数据
  int v, e;  // 顶点数和边数
  cin >> v >> e;
  int x, y, k;  // 边的起点、终点、权值
  // 填充一个默认最大值
  vector<vector<int>> grid(v + 1, vector<int>(v + 1, INT_MAX));
  for (int i = 0; i < e; i++) {
    cin >> x >> y >> k;
    // 因为是双向图，所以两边都要填上
    grid[x][y] = k;
    grid[y][x] = k;
  }
  // 构建minDist数组
  vector<int> minDist(v + 1, INT_MAX);
  minDist[1] = 0;  // 起点的距离为0 选取第一个顶点作为起点
  // 创建visited数组，用于标记是否访问过
  vector<bool> visited(v + 1, false);
  // 只需要循环n-1次，建立n-1条边，即可把n个顶点连通
  for (int i = 1; i < v; i++) {
    // prim三部曲
    int cur = -1;                   // 选中的顶点加入最小生成树
    int minVal = INT_MAX;           // 最小权值
    for (int j = 1; j <= v; j++) {  // 遍历所有顶点
      // 选取最小生成树节点的条件：
      // 1. 未访问过
      // 2. 距离最小生成树最近的节点
      if (!visited[j] && minDist[j] < minVal) {  // 未访问过，且权值最小
        cur = j;
        minVal = minDist[j];
      }
    }
    // 第二步：加入最小生成树
    visited[cur] = true;  // 标记为已访问
    // 更新最小生成树的距离minDist数组
    for (int j = 1; j <= v; j++) {  // 遍历所有顶点
      // 更新条件：
      // 1. 未访问过
      // 2. 距离cur最近的节点
      if (!visited[j] && grid[cur][j] < minDist[j]) {
        minDist[j] = grid[cur][j];
      }
    }
  }
  // 输出结果
  int result = 0;
  for (int j = 1; j <= v; j++) {
    result += minDist[j];
  }
  cout << result << endl;
  return 0;
}
